home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 2: CDPD 1 / Almathera Ten on Ten - Disc 2: CDPD 1.iso / pd / 026-050 / 042 / mg1a / display.c < prev    next >
C/C++ Source or Header  |  1995-03-13  |  21KB  |  779 lines
  1. /*
  2.  * The functions in this file handle redisplay. The
  3.  * redisplay system knows almost nothing about the editing
  4.  * process; the editing functions do, however, set some
  5.  * hints to eliminate a lot of the grinding. There is more
  6.  * that can be done; the "vtputc" interface is a real
  7.  * pig. Two conditional compilation flags; the GOSLING
  8.  * flag enables dynamic programming redisplay, using the
  9.  * algorithm published by Jim Gosling in SIGOA. The MEMMAP
  10.  * changes things around for memory mapped video. With
  11.  * both off, the terminal is a VT52.
  12.  */
  13. #include    "def.h"
  14.  
  15. /*
  16.  * You can change these back to the types
  17.  * implied by the name if you get tight for space. If you
  18.  * make both of them "int" you get better code on the VAX.
  19.  * They do nothing if this is not Gosling redisplay, except
  20.  * for change the size of a structure that isn't used.
  21.  * A bit of a cheat.
  22.  */
  23. /* These defines really belong in sysdef.h */
  24. #ifndef XCHAR
  25. #  define    XCHAR    int
  26. #  define    XSHORT    int
  27. #endif
  28.  
  29. #ifdef    STANDOUT_GLITCH
  30. extern int SG;                /* number of standout glitches    */
  31. #endif
  32.  
  33. /*
  34.  * A video structure always holds
  35.  * an array of characters whose length is equal to
  36.  * the longest line possible. Only some of this is
  37.  * used if "ncol" isn't the same as "NCOL".
  38.  */
  39. typedef    struct    {
  40.     short    v_hash;            /* Hash code, for compares.    */
  41.     short    v_flag;            /* Flag word.            */
  42.     short    v_color;        /* Color of the line.        */
  43.     XSHORT    v_cost;            /* Cost of display.        */
  44.     char    v_text[NCOL];        /* The actual characters.    */
  45. }    VIDEO;
  46.  
  47. #define    VFCHG    0x0001            /* Changed.            */
  48. #define    VFHBAD    0x0002            /* Hash and cost are bad.    */
  49.  
  50. /*
  51.  * SCORE structures hold the optimal
  52.  * trace trajectory, and the cost of redisplay, when
  53.  * the dynamic programming redisplay code is used.
  54.  * If no fancy redisplay, this isn't used. The trace index
  55.  * fields can be "char", and the score a "short", but
  56.  * this makes the code worse on the VAX.
  57.  */
  58. typedef    struct    {
  59.     XCHAR    s_itrace;        /* "i" index for track back.    */
  60.     XCHAR    s_jtrace;        /* "j" index for trace back.    */
  61.     XSHORT    s_cost;            /* Display cost.        */
  62. }    SCORE;
  63.  
  64. int    sgarbf    = TRUE;            /* TRUE if screen is garbage.    */
  65. int    vtrow    = 0;            /* Virtual cursor row.        */
  66. int    vtcol    = 0;            /* Virtual cursor column.    */
  67. int    tthue    = CNONE;        /* Current color.        */
  68. int    ttrow    = HUGE;            /* Physical cursor row.        */
  69. int    ttcol    = HUGE;            /* Physical cursor column.    */
  70. int    tttop    = HUGE;            /* Top of scroll region.    */
  71. int    ttbot    = HUGE;            /* Bottom of scroll region.    */
  72.  
  73. VIDEO    *vscreen[NROW-1];        /* Edge vector, virtual.    */
  74. VIDEO    *pscreen[NROW-1];        /* Edge vector, physical.    */
  75. VIDEO    video[2*(NROW-1)];        /* Actual screen data.        */
  76. VIDEO    blanks;                /* Blank line image.        */
  77.  
  78. #ifdef    GOSLING
  79. /*
  80.  * This matrix is written as an array because
  81.  * we do funny things in the "setscores" routine, which
  82.  * is very compute intensive, to make the subscripts go away.
  83.  * It would be "SCORE    score[NROW][NROW]" in old speak.
  84.  * Look at "setscores" to understand what is up.
  85.  */
  86. SCORE    score[NROW*NROW];
  87. #endif
  88.  
  89. /*
  90.  * Initialize the data structures used
  91.  * by the display code. The edge vectors used
  92.  * to access the screens are set up. The operating
  93.  * system's terminal I/O channel is set up. Fill the
  94.  * "blanks" array with ASCII blanks. The rest is done
  95.  * at compile time. The original window is marked
  96.  * as needing full update, and the physical screen
  97.  * is marked as garbage, so all the right stuff happens
  98.  * on the first call to redisplay.
  99.  */
  100. vtinit() {
  101.     register VIDEO    *vp;
  102.     register int    i;
  103.  
  104.     ttopen();
  105.     ttinit();
  106.     vp = &video[0];
  107.     for (i=0; i<NROW-1; ++i) {
  108.         vscreen[i] = vp;
  109.         ++vp;
  110.         pscreen[i] = vp;
  111.         ++vp;
  112.     }
  113.     blanks.v_color = CTEXT;
  114.     for (i=0; i<NCOL; ++i)
  115.         blanks.v_text[i] = ' ';
  116. }
  117.  
  118. /*
  119.  * Tidy up the virtual display system
  120.  * in anticipation of a return back to the host
  121.  * operating system. Right now all we do is position
  122.  * the cursor to the last line, erase the line, and
  123.  * close the terminal channel.
  124.  */
  125. vttidy() {
  126.     ttcolor(CTEXT);
  127.     ttnowindow();                /* No scroll window.    */
  128.     ttmove(nrow-1, 0);            /* Echo line.        */
  129.     tteeol();
  130.     tttidy();
  131.     ttflush();
  132.     ttclose();
  133. }
  134.  
  135. /*
  136.  * Move the virtual cursor to an origin
  137.  * 0 spot on the virtual display screen. I could
  138.  * store the column as a character pointer to the spot
  139.  * on the line, which would make "vtputc" a little bit
  140.  * more efficient. No checking for errors.
  141.  */
  142. vtmove(row, col) {
  143.     vtrow = row;
  144.     vtcol = col;
  145. }
  146.  
  147. /*
  148.  * Write a character to the virtual display,
  149.  * dealing with long lines and the display of unprintable
  150.  * things like control characters. Also expand tabs every 8
  151.  * columns. This code only puts printing characters into 
  152.  * the virtual display image. Special care must be taken when
  153.  * expanding tabs. On a screen whose width is not a multiple
  154.  * of 8, it is possible for the virtual cursor to hit the
  155.  * right margin before the next tab stop is reached. This
  156.  * makes the tab code loop if you are not careful.
  157.  * Three guesses how we found this.
  158.  */
  159. vtputc(c) register int c; {
  160.     register VIDEO    *vp;
  161.  
  162.     vp = vscreen[vtrow];
  163.     if (vtcol >= ncol)
  164.         vp->v_text[ncol-1] = '$';
  165.     else if (c == '\t') {
  166.         do {
  167.             vtputc(' ');
  168.         } while (vtcol<ncol && (vtcol&0x07)!=0);
  169.     } else if (ISCTRL(c) != FALSE) {
  170.         vtputc('^');
  171.         vtputc(c ^ 0x40);
  172.     } else
  173.         vp->v_text[vtcol++] = c;        
  174. }
  175.  
  176. /*
  177.  * Erase from the end of the
  178.  * software cursor to the end of the
  179.  * line on which the software cursor is
  180.  * located. The display routines will decide
  181.  * if a hardware erase to end of line command
  182.  * should be used to display this.
  183.  */
  184. vteeol() {
  185.     register VIDEO    *vp;
  186.  
  187.     vp = vscreen[vtrow];
  188.     while (vtcol < ncol)
  189.         vp->v_text[vtcol++] = ' ';
  190. }
  191.  
  192. /*
  193.  * Make sure that the display is
  194.  * right. This is a three part process. First,
  195.  * scan through all of the windows looking for dirty
  196.  * ones. Check the framing, and refresh the screen.
  197.  * Second, make sure that "currow" and "curcol" are
  198.  * correct for the current window. Third, make the
  199.  * virtual and physical screens the same.
  200.  */
  201. VOID
  202. update() {
  203.     register LINE    *lp;
  204.     register WINDOW    *wp;
  205.     register VIDEO    *vp1;
  206.     register VIDEO    *vp2;
  207.     register int    i;
  208.     register int    j;
  209.     register int    c;
  210.     register int    hflag;
  211.     register int    currow;
  212.     register int    curcol;
  213.     register int    offs;
  214.     register int    size;
  215.     VOID traceback ();
  216.     VOID uline ();
  217.  
  218.     if (typeahead()) return;
  219.     if (sgarbf) {                /* must update everything */
  220.         wp = wheadp; 
  221.         while(wp != NULL) {
  222.             wp->w_flag |= WFMODE | WFHARD;
  223.             wp = wp->w_wndp;
  224.         }
  225.     }
  226.     hflag = FALSE;                /* Not hard.        */
  227.     wp = wheadp;
  228.     while (wp != NULL) {
  229.         if (wp->w_flag != 0) {        /* Need update.        */
  230.             if ((wp->w_flag&WFFORCE) == 0) {
  231.                 lp = wp->w_linep;
  232.                 for (i=0; i<wp->w_ntrows; ++i) {
  233.                     if (lp == wp->w_dotp)
  234.                         goto out;
  235.                     if (lp == wp->w_bufp->b_linep)
  236.                         break;
  237.                     lp = lforw(lp);
  238.                 }
  239.             }
  240.             i = wp->w_force;    /* Reframe this one.    */
  241.             if (i > 0) {
  242.                 --i;
  243.                 if (i >= wp->w_ntrows)
  244.                     i = wp->w_ntrows-1;
  245.             } else if (i < 0) {
  246.                 i += wp->w_ntrows;
  247.                 if (i < 0)
  248.                     i = 0;
  249.             } else
  250.                 i = wp->w_ntrows/2;
  251.             lp = wp->w_dotp;
  252.             while (i!=0 && lback(lp)!=wp->w_bufp->b_linep) {
  253.                 --i;
  254.                 lp = lback(lp);
  255.             }
  256.             wp->w_linep = lp;
  257.             wp->w_flag |= WFHARD;    /* Force full.        */
  258.         out:
  259.             lp = wp->w_linep;    /* Try reduced update.    */
  260.             i  = wp->w_toprow;
  261.             if ((wp->w_flag&~WFMODE) == WFEDIT) {
  262.                 while (lp != wp->w_dotp) {
  263.                     ++i;
  264.                     lp = lforw(lp);
  265.                 }
  266.                 vscreen[i]->v_color = CTEXT;
  267.                 vscreen[i]->v_flag |= (VFCHG|VFHBAD);
  268.                 vtmove(i, 0);
  269.                 for (j=0; j<llength(lp); ++j)
  270.                     vtputc(lgetc(lp, j));
  271.                 vteeol();
  272.             } else if ((wp->w_flag&(WFEDIT|WFHARD)) != 0) {
  273.                 hflag = TRUE;
  274.                 while (i < wp->w_toprow+wp->w_ntrows) {
  275.                     vscreen[i]->v_color = CTEXT;
  276.                     vscreen[i]->v_flag |= (VFCHG|VFHBAD);
  277.                     vtmove(i, 0);
  278.                     if (lp != wp->w_bufp->b_linep) {
  279.                         for (j=0; j<llength(lp); ++j)
  280.                             vtputc(lgetc(lp, j));
  281.                         lp = lforw(lp);
  282.                     }
  283.                     vteeol();
  284.                     ++i;
  285.                 }
  286.             }
  287.             if ((wp->w_flag&WFMODE) != 0)
  288.                 modeline(wp);
  289.             wp->w_flag  = 0;
  290.             wp->w_force = 0;
  291.         }        
  292.         wp = wp->w_wndp;
  293.     }
  294.     lp = curwp->w_linep;            /* Cursor location.    */
  295.     currow = curwp->w_toprow;
  296.     while (lp != curwp->w_dotp) {
  297.         ++currow;
  298.         lp = lforw(lp);
  299.     }
  300.     curcol = 0;
  301.     i = 0;
  302.     while (i < curwp->w_doto) {
  303.         c = lgetc(lp, i++);
  304.         if (c == '\t')
  305.             curcol |= 0x07;
  306.         else if (ISCTRL(c) != FALSE)
  307.             ++curcol;
  308.         ++curcol;
  309.     }
  310.     if (curcol >= ncol)            /* Long line.        */
  311.         curcol = ncol-1;
  312.     if (sgarbf != FALSE) {            /* Screen is garbage.    */
  313.         sgarbf = FALSE;            /* Erase-page clears    */
  314.         epresf = FALSE;            /* the message area.    */
  315.         tttop  = HUGE;            /* Forget where you set    */
  316.         ttbot  = HUGE;            /* scroll region.    */
  317.         tthue  = CNONE;            /* Color unknown.    */
  318.         ttmove(0, 0);
  319.         tteeop();
  320.         for (i=0; i<nrow-1; ++i) {
  321.             uline(i, vscreen[i], &blanks);
  322.             ucopy(vscreen[i], pscreen[i]);
  323.         }
  324.         ttmove(currow, curcol);
  325.         ttflush();
  326.         return;
  327.     }
  328. #ifdef    GOSLING
  329.     if (hflag != FALSE) {            /* Hard update?        */
  330.         for (i=0; i<nrow-1; ++i) {    /* Compute hash data.    */
  331.             hash(vscreen[i]);
  332.             hash(pscreen[i]);
  333.         }
  334.         offs = 0;            /* Get top match.    */
  335.         while (offs != nrow-1) {
  336.             vp1 = vscreen[offs];
  337.             vp2 = pscreen[offs];
  338.             if (vp1->v_color != vp2->v_color
  339.             ||  vp1->v_hash  != vp2->v_hash)
  340.                 break;
  341.             uline(offs, vp1, vp2);
  342.             ucopy(vp1, vp2);
  343.             ++offs;
  344.         }
  345.         if (offs == nrow-1) {        /* Might get it all.    */
  346.             ttmove(currow, curcol);
  347.             ttflush();
  348.             return;
  349.         }
  350.         size = nrow-1;            /* Get bottom match.    */
  351.         while (size != offs) {
  352.             vp1 = vscreen[size-1];
  353.             vp2 = pscreen[size-1];
  354.             if (vp1->v_color != vp2->v_color
  355.             ||  vp1->v_hash  != vp2->v_hash)
  356.                 break;
  357.             uline(size-1, vp1, vp2);
  358.             ucopy(vp1, vp2);
  359.             --size;
  360.         }
  361.         if ((size -= offs) == 0)    /* Get screen size.    */
  362.             panic("Illegal screen size in update");
  363.         setscores(offs, size);        /* Do hard update.    */
  364.         traceback(offs, size, size, size);
  365.         for (i=0; i<size; ++i)
  366.             ucopy(vscreen[offs+i], pscreen[offs+i]);
  367.         ttmove(currow, curcol);
  368.         ttflush();
  369.         return;            
  370.     }
  371. #endif
  372.     for (i=0; i<nrow-1; ++i) {        /* Easy update.        */
  373.         vp1 = vscreen[i];
  374.         vp2 = pscreen[i];
  375.         if ((vp1->v_flag&VFCHG) != 0) {
  376.             uline(i, vp1, vp2);
  377.             ucopy(vp1, vp2);
  378.         }
  379.     }
  380.     ttmove(currow, curcol);
  381.     ttflush();
  382. }
  383.  
  384. /*
  385.  * Update a saved copy of a line,
  386.  * kept in a VIDEO structure. The "vvp" is
  387.  * the one in the "vscreen". The "pvp" is the one
  388.  * in the "pscreen". This is called to make the
  389.  * virtual and physical screens the same when
  390.  * display has done an update.
  391.  */
  392. ucopy(vvp, pvp) register VIDEO *vvp; register VIDEO *pvp; {
  393.  
  394.     vvp->v_flag &= ~VFCHG;            /* Changes done.    */
  395.     pvp->v_flag  = vvp->v_flag;        /* Update model.    */
  396.     pvp->v_hash  = vvp->v_hash;
  397.     pvp->v_cost  = vvp->v_cost;
  398.     pvp->v_color = vvp->v_color;
  399.     bcopy(vvp->v_text, pvp->v_text, ncol);
  400. }
  401.  
  402. /*
  403.  * Update a single line. This routine only
  404.  * uses basic functionality (no insert and delete character,
  405.  * but erase to end of line). The "vvp" points at the VIDEO
  406.  * structure for the line on the virtual screen, and the "pvp"
  407.  * is the same for the physical screen. Avoid erase to end of
  408.  * line when updating CMODE color lines, because of the way that
  409.  * reverse video works on most terminals.
  410.  */
  411. VOID uline(row, vvp, pvp) VIDEO *vvp; VIDEO *pvp; {
  412. #ifdef    MEMMAP
  413.     putline(row+1, 1, &vvp->v_text[0]);
  414. #else
  415.     register char    *cp1;
  416.     register char    *cp2;
  417.     register char    *cp3;
  418.     register char    *cp4;
  419.     register char    *cp5;
  420.     register int    nbflag;
  421.  
  422.     if (vvp->v_color != pvp->v_color) {    /* Wrong color, do a    */
  423.         ttmove(row, 0);            /* full redraw.        */
  424. #ifdef    STANDOUT_GLITCH
  425.         if (pvp->v_color != CTEXT && SG >= 0) tteeol();
  426. #endif
  427.         ttcolor(vvp->v_color);
  428. #ifdef    STANDOUT_GLITCH
  429.         cp1 = &vvp->v_text[SG > 0 ? SG : 0];
  430.         /* the odd code for SG==0 is to avoid putting the invisable
  431.          * glitch character on the next line.  
  432.          * (Hazeltine executive 80 model 30)
  433.          */
  434.         cp2 = &vvp->v_text[ncol - (SG >= 0 ? (SG!=0 ? SG : 1) : 0)];
  435. #else
  436.         cp1 = &vvp->v_text[0];
  437.         cp2 = &vvp->v_text[ncol];
  438. #endif
  439.         while (cp1 != cp2) {
  440.             ttputc(*cp1++);
  441.             ++ttcol;
  442.         }
  443. #ifndef    MOVE_STANDOUT
  444.         ttcolor(CTEXT);
  445. #endif
  446.         return;
  447.     }
  448.     cp1 = &vvp->v_text[0];            /* Compute left match.    */
  449.     cp2 = &pvp->v_text[0];
  450.     while (cp1!=&vvp->v_text[ncol] && cp1[0]==cp2[0]) {
  451.         ++cp1;
  452.         ++cp2;
  453.     }
  454.     if (cp1 == &vvp->v_text[ncol])        /* All equal.        */
  455.         return;
  456.     nbflag = FALSE;
  457.     cp3 = &vvp->v_text[ncol];        /* Compute right match.    */
  458.     cp4 = &pvp->v_text[ncol];
  459.     while (cp3[-1] == cp4[-1]) {
  460.         --cp3;
  461.         --cp4;
  462.         if (cp3[0] != ' ')        /* Note non-blanks in    */
  463.             nbflag = TRUE;        /* the right match.    */
  464.     }
  465.     cp5 = cp3;                /* Is erase good?    */
  466.     if (nbflag==FALSE && vvp->v_color==CTEXT) {
  467.         while (cp5!=cp1 && cp5[-1]==' ')
  468.             --cp5;
  469.         /* Alcyon hack */
  470.         if ((int)(cp3-cp5) <= tceeol)
  471.             cp5 = cp3;
  472.     }
  473.     /* Alcyon hack */
  474.     ttmove(row, (int)(cp1-&vvp->v_text[0]));
  475. #ifdef    STANDOUT_GLITCH
  476.     if (vvp->v_color != CTEXT && SG > 0) {
  477.         if(cp1 < &vvp->v_text[SG]) cp1 = &vvp->v_text[SG];
  478.         if(cp5 > &vvp->v_text[ncol-SG]) cp5 = &vvp->v_text[ncol-SG];
  479.     } else if (SG < 0)
  480. #endif
  481.     ttcolor(vvp->v_color);
  482.     while (cp1 != cp5) {
  483.         ttputc(*cp1++);
  484.         ++ttcol;
  485.     }
  486.     if (cp5 != cp3)                /* Do erase.        */
  487.         tteeol();
  488. #endif
  489. }
  490.  
  491. /*
  492.  * Redisplay the mode line for
  493.  * the window pointed to by the "wp".
  494.  * This is the only routine that has any idea
  495.  * of how the modeline is formatted. You can
  496.  * change the modeline format by hacking at
  497.  * this routine. Called by "update" any time
  498.  * there is a dirty window.
  499.  * Note that if STANDOUT_GLITCH is defined, first and last SG characters
  500.  * may never be seen.
  501.  */
  502. modeline(wp) register WINDOW *wp; {
  503.     register int    n;
  504.     register BUFFER    *bp;
  505.  
  506.     n = wp->w_toprow+wp->w_ntrows;        /* Location.        */
  507.     vscreen[n]->v_color = CMODE;        /* Mode line color.    */
  508.     vscreen[n]->v_flag |= (VFCHG|VFHBAD);    /* Recompute, display.    */
  509.     vtmove(n, 0);                /* Seek to right line.    */
  510.     bp = wp->w_bufp;
  511.     vtputc('-'); vtputc('-');
  512.     if ((bp->b_flag&BFCHG) != 0) {        /* "*" if changed.    */
  513.         vtputc('*'); vtputc('*');
  514.     } else {
  515.         vtputc('-'); vtputc('-');
  516.     }
  517.     vtputc('-');
  518.     n  = 5;
  519.     n += vtputs("MicroGnuEmacs:");
  520.     if (bp->b_bname[0] != 0) {
  521.         vtputc(' ');
  522.         ++n;
  523.         n += vtputs(&(bp->b_bname[0]));
  524.     }
  525.     while (n < 42) {            /* Pad out with blanks    */
  526.         vtputc(' ');
  527.         ++n;
  528.     }
  529.     vtputc('(');
  530.     ++n;
  531.     if (mode == 0) n += vtputs("Fundamental");
  532.     else {
  533.         if ((mode&MBSMAP) != 0) {
  534.             n += vtputs("bsmap");
  535.             if ((mode&~MBSMAP) != 0) {
  536.                 vtputc('-');
  537.                 ++n;
  538.             }
  539.         }
  540.         if ((mode&MFLOW) != 0) {
  541.             n += vtputs("flow");
  542.             if ((mode&~(MFLOW|MBSMAP)) != 0) {
  543.                 vtputc('-');
  544.                 ++n;
  545.             }
  546.         }
  547.         if ((mode&MINDENT) != 0) {
  548.             n += vtputs("indent");
  549.             if ((mode&~(MINDENT|MFLOW|MBSMAP)) != 0) {
  550.                 vtputc('-');
  551.                 ++n;
  552.             }
  553.         }
  554.         if ((mode&MFILL) != 0)
  555.             n += vtputs("fill");
  556.     }
  557.     vtputc(')');
  558.     ++n;
  559.     while (n < ncol) {            /* Pad out.        */
  560.         vtputc('-');
  561.         ++n;
  562.     }
  563. }
  564. /*
  565.  * output a string to the mode line, report how long it was.
  566.  */
  567. vtputs(s) register char *s; {
  568.     register int n = 0;
  569.  
  570.     while (*s != '\0') {
  571.         vtputc(*s++);
  572.         ++n;
  573.     }
  574.     return n;
  575. }
  576. #ifdef    GOSLING
  577. /*
  578.  * Compute the hash code for
  579.  * the line pointed to by the "vp". Recompute
  580.  * it if necessary. Also set the approximate redisplay
  581.  * cost. The validity of the hash code is marked by
  582.  * a flag bit. The cost understand the advantages
  583.  * of erase to end of line. Tuned for the VAX
  584.  * by Bob McNamara; better than it used to be on
  585.  * just about any machine.
  586.  */
  587. hash(vp) register VIDEO *vp; {
  588.     register int    i;
  589.     register int    n;
  590.     register char    *s;
  591.  
  592.     if ((vp->v_flag&VFHBAD) != 0) {        /* Hash bad.        */
  593.         s = &vp->v_text[ncol-1];
  594.         for (i=ncol; i!=0; --i, --s)
  595.             if (*s != ' ')
  596.                 break;
  597.         n = ncol-i;            /* Erase cheaper?    */
  598.         if (n > tceeol)
  599.             n = tceeol;
  600.         vp->v_cost = i+n;        /* Bytes + blanks.    */
  601.         for (n=0; i!=0; --i, --s)
  602.             n = (n<<5) + n + *s;
  603.         vp->v_hash = n;            /* Hash code.        */
  604.         vp->v_flag &= ~VFHBAD;        /* Flag as all done.    */
  605.     }
  606. }
  607.  
  608. /*
  609.  * Compute the Insert-Delete
  610.  * cost matrix. The dynamic programming algorithm
  611.  * described by James Gosling is used. This code assumes
  612.  * that the line above the echo line is the last line involved
  613.  * in the scroll region. This is easy to arrange on the VT100
  614.  * because of the scrolling region. The "offs" is the origin 0
  615.  * offset of the first row in the virtual/physical screen that
  616.  * is being updated; the "size" is the length of the chunk of
  617.  * screen being updated. For a full screen update, use offs=0
  618.  * and size=nrow-1.
  619.  *
  620.  * Older versions of this code implemented the score matrix by
  621.  * a two dimensional array of SCORE nodes. This put all kinds of
  622.  * multiply instructions in the code! This version is written to
  623.  * use a linear array and pointers, and contains no multiplication
  624.  * at all. The code has been carefully looked at on the VAX, with
  625.  * only marginal checking on other machines for efficiency. In
  626.  * fact, this has been tuned twice! Bob McNamara tuned it even
  627.  * more for the VAX, which is a big issue for him because of
  628.  * the 66 line X displays.
  629.  *
  630.  * On some machines, replacing the "for (i=1; i<=size; ++i)" with
  631.  * i = 1; do { } while (++i <=size)" will make the code quite a
  632.  * bit better; but it looks ugly.
  633.  */
  634. setscores(offs, size) {
  635.     register SCORE    *sp;
  636.     SCORE        *sp1;
  637.     register int    tempcost;
  638.     register int    bestcost;
  639.     register int    j;
  640.     register int    i;
  641.     register VIDEO    **vp;
  642.     VIDEO        **pp, **vbase, **pbase;
  643.  
  644.     vbase = &vscreen[offs-1];        /* By hand CSE's.    */
  645.     pbase = &pscreen[offs-1];
  646.     score[0].s_itrace = 0;            /* [0, 0]        */
  647.     score[0].s_jtrace = 0;
  648.     score[0].s_cost   = 0;
  649.     sp = &score[1];                /* Row 0, inserts.    */
  650.     tempcost = 0;
  651.     vp = &vbase[1];
  652.     for (j=1; j<=size; ++j) {
  653.         sp->s_itrace = 0;
  654.         sp->s_jtrace = j-1;
  655.         tempcost += tcinsl;
  656.         tempcost += (*vp)->v_cost;
  657.         sp->s_cost = tempcost;
  658.         ++vp;
  659.         ++sp;
  660.     }
  661.     sp = &score[NROW];            /* Column 0, deletes.    */
  662.     tempcost = 0;
  663.     for (i=1; i<=size; ++i) {
  664.         sp->s_itrace = i-1;
  665.         sp->s_jtrace = 0;
  666.         tempcost  += tcdell;
  667.         sp->s_cost = tempcost;
  668.         sp += NROW;
  669.     }
  670.     sp1 = &score[NROW+1];            /* [1, 1].        */
  671.     pp = &pbase[1];
  672.     for (i=1; i<=size; ++i) {
  673.         sp = sp1;
  674.         vp = &vbase[1];
  675.         for (j=1; j<=size; ++j) {
  676.             sp->s_itrace = i-1;
  677.             sp->s_jtrace = j;
  678.             bestcost = (sp-NROW)->s_cost;
  679.             if (j != size)        /* Cd(A[i])=0 @ Dis.    */
  680.                 bestcost += tcdell;
  681.             tempcost = (sp-1)->s_cost;
  682.             tempcost += (*vp)->v_cost;
  683.             if (i != size)        /* Ci(B[j])=0 @ Dsj.    */
  684.                 tempcost += tcinsl;
  685.             if (tempcost < bestcost) {
  686.                 sp->s_itrace = i;
  687.                 sp->s_jtrace = j-1;
  688.                 bestcost = tempcost;
  689.             }
  690.             tempcost = (sp-NROW-1)->s_cost;
  691.             if ((*pp)->v_color != (*vp)->v_color
  692.             ||  (*pp)->v_hash  != (*vp)->v_hash)
  693.                 tempcost += (*vp)->v_cost;
  694.             if (tempcost < bestcost) {
  695.                 sp->s_itrace = i-1;
  696.                 sp->s_jtrace = j-1;
  697.                 bestcost = tempcost;
  698.             }
  699.             sp->s_cost = bestcost;
  700.             ++sp;            /* Next column.        */
  701.             ++vp;
  702.         }
  703.         ++pp;
  704.         sp1 += NROW;            /* Next row.        */
  705.     }
  706. }
  707.  
  708. /*
  709.  * Trace back through the dynamic programming cost
  710.  * matrix, and update the screen using an optimal sequence
  711.  * of redraws, insert lines, and delete lines. The "offs" is
  712.  * the origin 0 offset of the chunk of the screen we are about to
  713.  * update. The "i" and "j" are always started in the lower right
  714.  * corner of the matrix, and imply the size of the screen.
  715.  * A full screen traceback is called with offs=0 and i=j=nrow-1.
  716.  * There is some do-it-yourself double subscripting here,
  717.  * which is acceptable because this routine is much less compute
  718.  * intensive then the code that builds the score matrix!
  719.  */
  720. VOID traceback(offs, size, i, j) {
  721.     register int    itrace;
  722.     register int    jtrace;
  723.     register int    k;
  724.     register int    ninsl;
  725.     register int    ndraw;
  726.     register int    ndell;
  727.  
  728.     if (i==0 && j==0)            /* End of update.    */
  729.         return;
  730.     itrace = score[(NROW*i) + j].s_itrace;
  731.     jtrace = score[(NROW*i) + j].s_jtrace;
  732.     if (itrace == i) {            /* [i, j-1]        */
  733.         ninsl = 0;            /* Collect inserts.    */
  734.         if (i != size)
  735.             ninsl = 1;
  736.         ndraw = 1;
  737.         while (itrace!=0 || jtrace!=0) {
  738.             if (score[(NROW*itrace) + jtrace].s_itrace != itrace)
  739.                 break;
  740.             jtrace = score[(NROW*itrace) + jtrace].s_jtrace;
  741.             if (i != size)
  742.                 ++ninsl;
  743.             ++ndraw;
  744.         }
  745.         traceback(offs, size, itrace, jtrace);
  746.         if (ninsl != 0) {
  747.             ttcolor(CTEXT);
  748.             ttinsl(offs+j-ninsl, offs+size-1, ninsl);
  749.         }
  750.         do {                /* B[j], A[j] blank.    */
  751.             k = offs+j-ndraw;
  752.             uline(k, vscreen[k], &blanks);
  753.         } while (--ndraw);
  754.         return;
  755.     }
  756.     if (jtrace == j) {            /* [i-1, j]        */
  757.         ndell = 0;            /* Collect deletes.    */
  758.         if (j != size)
  759.             ndell = 1;
  760.         while (itrace!=0 || jtrace!=0) {
  761.             if (score[(NROW*itrace) + jtrace].s_jtrace != jtrace)
  762.                 break;
  763.             itrace = score[(NROW*itrace) + jtrace].s_itrace;
  764.             if (j != size)
  765.                 ++ndell;
  766.         }
  767.         if (ndell != 0) {
  768.             ttcolor(CTEXT);
  769.             ttdell(offs+i-ndell, offs+size-1, ndell);
  770.         }
  771.         traceback(offs, size, itrace, jtrace);
  772.         return;
  773.     }
  774.     traceback(offs, size, itrace, jtrace);
  775.     k = offs+j-1;
  776.     uline(k, vscreen[k], pscreen[offs+i-1]);
  777. }
  778. #endif
  779.